package com.gofaraway.service.左神算法课.heap;

import static com.gofaraway.service.utils.AlgorithmUtils.swap;
import static com.gofaraway.service.左神算法课.heap.Code02_Heap.heapInsert;
import static com.gofaraway.service.左神算法课.heap.Code02_Heap.heapify;

/**
 * 实现堆排序
 *
 * @author ChenPeng
 * @since 2025/2/16 16:40
 */
public class Code03_HeapSort {


    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        //将数组转成成 满足大根堆的数组
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }

        int heapSize = arr.length;
        // 0 位置的数是 最大值
        swap(arr, 0, --heapSize);

        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
}
